package _back_tracking

import org.junit.Assert
import org.junit.Test

/*
https://programmercarl.com/0216.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CIII.html
https://leetcode.cn/problems/combination-sum-iii/description/

 216. 组合总和 III
 找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
 - 只使用数字1到9
 - 每个数字 最多使用一次
 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

 示例 1:
 输入: k = 3, n = 7
 输出: [[1,2,4]]
 解释:
 1 + 2 + 4 = 7
 没有其他符合的组合了。
 
 示例 2:
 输入: k = 3, n = 9
 输出: [[1,2,6], [1,3,5], [2,3,4]]
 解释:
 1 + 2 + 6 = 9
 1 + 3 + 5 = 9
 2 + 3 + 4 = 9
 没有其他符合的组合了。

 示例 3:
 输入: k = 4, n = 1
 输出: []
 */
class leetcode_216 {
    @Test
    fun test_1() {
        val actual = combinationSum3(3, 7)
        val expect = arrayListOf(arrayListOf(1, 2, 4))
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_2() {
        val actual = combinationSum3(3, 9)
        val expect = arrayListOf(arrayListOf(1, 2, 6), arrayListOf(1, 3, 5), arrayListOf(2, 3, 4))
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_3() {
        val actual = combinationSum3(4, 1)
        val expect: List<List<Int>> = ArrayList<ArrayList<Int>>()
        Assert.assertEquals(expect.toString(), actual.toString())
    }
    fun combinationSum3(k: Int, n: Int): List<List<Int>> {
        /*
        回溯法
        1 注意：组合的元素只能从1 到 9
        2 sum, 一维数组，二维数组
         */
        val result: ArrayList<ArrayList<Int>> = ArrayList<ArrayList<Int>>()
        backtracking(k, n, 1, 0, ArrayList<Int>(), result)
        return result
    }

    private fun backtracking(k: Int, targetSum: Int, start: Int, currentSum: Int, path: ArrayList<Int>, result: ArrayList<ArrayList<Int>>) {
        // 时间复杂度: O(n 2^n)
        // 空间复杂度: O(n)
        // 终止条件

        // 剪枝操作2
        // if(sum > n){
        //     return
        // }
        if (path.size == k) {
            // 收集结果
            if (currentSum == targetSum) {
                val items: ArrayList<Int> = ArrayList<Int>()
                items.addAll(path)
                result.add(items)
            }
            return
        }

        // for(i in start .. n){ // [start, 9]
        // k相当于树的深度
        // 剪枝操作1
        for (i in start..(9 - (k - path.size) + 1)) { // [start, 9 - (k - path.size) + 1]
            // 处理条件
            // 剪枝操作2
            val newSum = currentSum + i
            if (newSum > targetSum) {
                // TODO:此处是return 不是 break
                return
            }
            path.add(i)
            // 递归
            // 因为元素可以不重复，start 为i+1
            backtracking(k, targetSum, i + 1, newSum, path, result)
            // 回溯
            path.remove(i)
        }
    }
}